/*
题目: 所有可能的路径
给你一个有 n 个节点的 有向无环图（DAG），请你找出所有从节点 0 到节点 n-1 的路径并输出（不要求按特定顺序）

 graph[i] 是一个从节点 i 可以访问的所有节点的列表（即从节点 i 到节点 graph[i][j]存在一条有向边）。

 https://leetcode.cn/problems/all-paths-from-source-to-target/description/
 */
public class AllPathsSourceTarget {
    List<List<Integer>> src = new ArrayList<> ();
    int n ;

    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        // 深度优先遍历
        n = graph.length;
        dfs(graph, 0, new boolean[graph.length], new ArrayList<>());
        return src;
    }

    public void dfs(int[][] graph, int pos, boolean[] visited, List<Integer> path) {
        visited[pos] = true;
        path.add(pos);
        if (pos == n - 1) {
            src.add(new ArrayList<>(path));
        }

        for (int i = 0; i < graph[pos].length; i ++) {
            int j = graph[pos][i];
            if (!visited[j]) {
                dfs(graph, j, visited, path);
                visited[j] = false;
                path.remove(path.size() - 1);
            }
        }
    }
}
